Note: this is not to be confused with the Naccache–Stern knapsack cryptosystem.
The Naccache–Stern cryptosystem is a homomorphic public-key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was discovered by David Naccache and Jacques Stern in 1998.
Contents |
Like many public key cryptosystems, this scheme works in the group where n is a product of two large primes. This scheme is homomorphic and hence malleable.
The public key is the numbers σ,n,g and the private key is the pair p,q.
When k=1 this is essentially the Benaloh cryptosystem.
This system allows encryption of a message m in the group .
Then E(m) is an encryption of the message m.
To decrypt, we first find m mod pi for each i, and then we apply the Chinese remainder theorem to calculate m mod .
Given a ciphertext c, to decrypt, we calculate
where .
The semantic security of the Naccache–Stern cryptosystem rests on an extension of the quadratic residuosity problem known as the higher residuosity problem.
|